
//  Definition for a binary tree node.
class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val)
        this.left = (left === undefined ? null : left)
        this.right = (right === undefined ? null : right)
    }
}


//  112. 路径总和

// 递归
function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
    // 为空直接返回false
    if (!root) return false;

    // 如果节点为根节点 那么判断值是否和目标值相同
    if (!root.left && !root.right) return targetSum === root.val;

    // 如果 目标值减去节点值 后返回true，如果左节点返回false则去判断目标值减去节点值是否存在一条路径相加为目标值
    // 划分子问题
    return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
};